package algorithmlearn.sort;

import java.util.*;

/**
 * 数组全排列
 * 1.递归实现
 */
public class ArrayPermute {
    static int num = 0;

    public static void main(String[] args) {

        Integer[] arr = {1, 2, 3, 4, 5};
        indexPermute(arr, 0);
    }

    /**
     * 方法1  递归 回溯
     *
     * @param arr   需要排序的数组
     * @param index 对第几位进行排序（0~（n-1）是已经排好的， index位置可选值，为index之后的任选一个）
     */
    private static void indexPermute(Integer[] arr, int index) {
        if (index == arr.length - 1) {
            System.out.println((++num) + " : " + Arrays.toString(arr));
        }
        for (int i = index; i < arr.length; i++) {
            int temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
            indexPermute(arr, index + 1);
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}
